import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 三石
 * Date: 2022-09-29
 * Time: 0:00
 */
public class MyStack {


    //定义一个数组表示栈\
    public int[] elem;

    // 存储的有效的数据个数  也可以表示当前可以存放数据元素的下标+1
    public int usedSize;

    public static final int DEFAULT_CAPACITY = 10; //final定义的数不可修改（类似于C语言中的const）
    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
    }

    /**
     * 用队列实现栈
     */
    Queue<Integer> qu1;
    Queue<Integer> qu2;
    public int usedsize;
    public void Mystack(){
        qu1=new LinkedList<>();
        qu2=new LinkedList<>();
    }

    //入栈
    public void push2(int x){
        if (!qu1.isEmpty()){  //qu1不为空
            qu1.offer(x);
        }else  if (!qu2.isEmpty()){  //qu2不为空
            qu2.offer(x);
        }else {         //qu1和qu2都不为空
            qu1.offer(x);
        }
        usedsize++;
    }
    //出栈
    public int pop2(){
        if (empty()){  //两个对列都为空
            return -1;
        }
        if (!qu1.isEmpty()){
            //qu1不为空，则需要从qu1倒出usedsize-1个元素到qu2
            int cursize=qu1.size();
            for (int i=0;i<cursize-1;i++){
                qu2.offer(qu1.poll());
            }
            usedsize--;
            return qu1.poll(); //此时qu1剩下最后一个元素，直接出栈
        }else {  //说明qu1为空，qu2不为空
            int cursize=qu2.size();
            for (int i=0;i<cursize-1;i++){
                qu1.offer(qu2.poll());
            }
            usedsize--;
            return qu2.poll();
        }
    }
    //peek
    public int top(){
        if (empty()){
            return -1;
        }
        if (!qu1.isEmpty()){
            int cur=qu1.size(); //usedsize会变化，所以需要定义cur记住usedsize的初始值
            int ret=-1;   //ret是中间用来记录每一个poll出来的值
            for (int i=0;i<cur;i++){
                ret=qu1.poll();
                qu2.offer(ret); //用另一个队列储存
            }
            return ret;
        }else {
            int curSize = qu2.size();
            int ret = -1;
            for (int i = 0; i < curSize; i++) {
                ret = qu2.poll();
                qu1.offer(ret);
            }
            return ret;
        }
    }

    public boolean empty() {
        return usedSize == 0;
    }

    /**
     * 后缀表达式计算
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (String x:tokens)
        if (!isOperation(x)){
            return -1;
        }else {
            int number2=pop();
            int number1=pop();
            switch (x){
                case "+":
                     push(number1+number2);
                     break;
                case "-":
                     push(number1-number2);
                     break;
                case "*":
                     push(number1*number2);
                    break;
                case "/":
                     push(number1/number2);
                     break;
            }
        }
        return pop();
    }
    //判断是不是加减乘除法
    private boolean isOperation(String opera){
        if (opera.equals("+")||opera.equals("-")||opera.equals("*")||opera.equals("/")){
            return true;
        }
        return false;
    }

    /**
     * 删除栈顶元素
     * @return
     */
    public int pop(){
        if(isempty()) {
            System.out.println("栈为空了！");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }

    /**
     * 获取栈顶元素 但是不删除
     * @return
     */
    public int peek() {
        if(isempty()) {
            System.out.println("栈为空了！");
        }
        return elem[usedSize-1];
    }

    /**
     * 获取usedsize
     */
    public int getUsedSize(){
        return usedSize;
    }

    /**
     * 输出
     */
    public void display(){
        while (!isempty()){
            System.out.print(elem[usedSize-1]+" ");
            usedSize--;
        }
    }

    /**
     * 压栈
     */
    public int  push(int val){
        if(isfull()){
            elem=Arrays.copyOf(elem,2*elem.length); //则栈为满，需要扩容
        }
        elem[usedSize]=val;
        usedSize++;
        return val;
    }


    /**
     * 判断栈是否为满
     */
    public boolean isfull(){
        if (usedSize==elem.length){  //如果elem的长度等于usesize
            return true;
        }
        return false;
    }


    /**
     * 判断栈是否为空
     */
    public boolean isempty(){
        return usedSize==0;
    }

    /**
     *  判断括号是否匹配
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length();i++) {
            char ch = s.charAt(i); //获取i下标的元素
            if(ch == '{' || ch == '(' || ch == '[') {
                stack.push(ch); //左括号，入栈操作
            }else {
                //说明ch里面   是右括号
                if(stack.empty()) {
                    //判断栈是否为空，若为空，则右括号多！
                    return false;
                }
                //若栈不为空，需要拿栈顶元素进行比较是否相匹配
                char top = stack.peek();
                if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') {
                    //只能说明 当前的字符是匹配的
                    stack.pop(); //匹配，则出栈
                }else{
                    //左右括号不匹配
                    return false;
                }
            }
        }
        if(stack.empty()) {
            return true;
        }else{
            //左括号多
            return false;
        }
    }
}

